/*
    Author: Christopher Diggins
    License: MIT Licence 1.0
    Website: http://www.cdiggins.com
*/

#ifndef CVML_STACK_HPP
#define CVML_STACK_HPP

/// This is a slow and simple stack class.
/// It should be optimized some day, but for 
/// now it will have to do. 
template<typename T, int BUFF_SIZE = 100>
struct Stack
{
    template<typename U, int SIZE>
    struct Buffer {
        Buffer(Buffer* _prev = NULL) 
            : next(NULL), prev(_prev), cnt(0) 
        { 
        }
        Buffer* next;
        Buffer* prev;
        U data[SIZE];
        int cnt;
		bool IsFull() const {
			return cnt == SIZE - 1;
		}
		bool IsEmpty() const {
			return cnt == 0;
		}
		U& Top() {
			Assert(!IsEmpty());
			return data[cnt-1];
		}
		void Pop() {
			Assert(!IsEmpty());
			--cnt;
		}
		void Push(const U& x) {
			Assert(!IsFull());
			data[cnt++] = x;
		}
		int Size() const {
			return cnt;
		}
		bool operator==(const Buffer& x) const {
			if (Size() != x.Size())
				return false;
			for (int i=0; i < Size(); ++i)
				if (!(data[i] == x.data[i]))
					return false;
			return true;
		}
    };
    
    typedef Buffer<T, BUFF_SIZE> BufferT;
    BufferT* cur;

	Stack()
		: cur(NULL)
	{ }

	Stack(const Stack& x) 
		: cur(NULL)
	{
		PushAll(x);
	}

	void PushAll(const Stack& x) {
		BufferT* tmp = x.cur;
		while (tmp != NULL && tmp->prev != NULL) {
			tmp = tmp->prev;
		}
		while (tmp != NULL) {
			for (int i=0; i < tmp->Size(); ++i) {
				Push(tmp->data[i]);
			}
			tmp = tmp->next;
		}
	}

	void Underflow() {
        Error("a stack underflow error occured");
    }

	void Clear() {
		while (!IsEmpty())
			Pop();
	}

    void Pop() {
		Assert(cur != NULL);
		int n = Size();
		Assert(n > 0);
		cur->Pop();
		if (cur->IsEmpty())
		{
			BufferT* tmp = cur;
			cur = cur->prev;
			if (cur != NULL)
				 cur->next = NULL;
			delete tmp;
		}
		Assert(Size() == n - 1);
    }

    T& Top()
    {
		Assert(cur != NULL);
		Assert(Size() > 0);
        return cur->Top();
    }

    T Pull()
    {
		T x = Top();
		Pop();
        return x;
    }

    void Push(const T& x)
    {        
		int n = Size();
        if (cur == NULL)
			cur = new BufferT(NULL);
		if (cur->IsFull()) {
			cur->next = new BufferT(cur);
			cur = cur->next;			
		}
		cur->Push(x);
		Assert(Size() == n + 1);
    }

    T& Below(int n) 
    {
		Assert(n < Size());
		Assert(n >= 0);
        return Below(cur, n);
    }

    T& Below(BufferT* buff, int n) {
		Assert(buff != NULL);
		if (n >= buff->cnt) {
			return Below(buff->prev, n - buff->cnt);
		}
		else {
			return buff->data[buff->cnt - n - 1];
		}
    }

    void Swap() 
    {
        T tmp = Pull();
        T tmp2 = Pull();
        Push(tmp);
        Push(tmp2);
    }

	int Size()
	{
		int r = 0;	
		for (BufferT* tmp = cur; tmp != NULL; tmp = tmp->prev) {
			r += tmp->cnt;
		}
		return r;
	}

	bool IsEmpty()
	{
		return cur == NULL;
	}
	
	bool operator==(const Stack& x)
	{
		BufferT* tmp1 = cur;
		BufferT* tmp2 = x.cur;
		while (tmp1 != NULL && tmp2 != NULL)
		{
			if (!(*tmp1 == *tmp2))
				return false;
			tmp1 = tmp1->next;
			tmp2 = tmp2->next;
		}
		if (tmp1 != NULL || tmp2 != NULL)
			return false;
		return true;
	}
};

#endif
